import java.util.Arrays;
import java.util.Stack;

public class Sort {

    public void InsertSort(int []array){

        for(int i=1;i<array.length;i++){
            int tmp=array[i];
            int j=i-1;
            for(;j>0;j--){
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;//防止当tmp的值为最小时在循环中不好赋值
        }
    }
    public void InsertSort1(int []array){

        for(int i=1;i<array.length;i++){
            int tmp=array[i];
            for(int j=i-1;j>=-1;j--){
                if(j==-1){//当tmp为最小时 j=-1 会越界 可以在循环外赋值
                    array[j+1]=tmp;
                    break;
                }
                if(array[j]>tmp){
                    array[j+1]=array[j];
                }else{//相等和 tmp>arr[j]是一样的顺序设置
                    array[j+1]=tmp;
                    break;
                }
            }
        }
    }


    public void ShellSort(int []array){
        int gap=array.length;
        while(gap>1){
            gap=gap/2;
            shell(gap,array);
        }

    }

    private void shell(int gap,int []array){
        //i++交替进行排序
        for (int i=gap;i<array.length;i++){ //从gap位置往回排序，每次加一间隔gap往回排序
            int tmp=array[i];
            int j=i-gap;
            for(;j>-1;j=j-gap){// j从间隔处进行排序
                if(array[j]>tmp){//间隔前的数大于要新排序的数时向后移动一个间隔
                    array[j+gap]=array[j];
                }else{
                    array[j+gap]=tmp;//间隔前的数小于于要新排序的数时，就是有序的了，直接放入
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

    public int[] ShellSort1(int []array1){
        int []array= Arrays.copyOf(array1,array1.length);
        int gap=array.length;
        while(gap>1){
            gap=gap/2;
            shell(gap,array);
        }
        return array;
     }



//    private void shell(int gap,int []array){
//        //i++交替进行排序
//        for(int i=gap;i<array.length;i++){ //从gap位置往回排序，每次加一间隔gap往回排序
//            int tmp=array[i];
//            int j=i-gap;
//            for(;j>=0;j=j-gap){// j从间隔处进行排序
//                if(array[j]>tmp){
//                    array[j+gap]=array[j];
//                }else{
//                    array[j+gap]=tmp;
//                    break;
//                }
//            }
//            array[j+gap]=tmp;
//        }
//
//    }
//}

    public void selectSort(int[]array){//选择排序，O(N),不稳定
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            for(int j=i;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(i,minIndex,array);
        }
    }

    public void swap(int i,int j,int[]array){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

    public void bubbleSort(int []array){
        // i是进行排序的趟数
        for(int i=0;i<array.length;i++){
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]){
                    swap(j,j+1,array);
                }
            }
        }
    }

    public void bubbleSortOptimized(int []array){//用falg进行标记，如果程序已经有序提前退出
        // i是进行排序的趟数
        for(int i=0;i<array.length;i++){
            boolean flag=false;
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]){
                    swap(j,j+1,array);
                    flag=true;
                }
            }
            if(flag==false){
                break;
            }
        }

    }

    public void quickSort(int []array){

        quick(array,0,array.length-1);
    }
    private void quick(int []array,int left,int right){//进行左右树的递归
        if(left>=right)return;
        if(right-left<=10){//当数据量小的时候换成直接插入排序，防止递归过多
            intervalInsertSort(array, left, right);
        }
        int mid=mid(array, left, right);
        swap(mid,left,array);
    int por=partition(array,left,right);
    quick(array,left,por-1);//左树
    quick(array,por+1,right);//右树
    }

    public void quickSort1(int []array){//非递归实现
        int left=0;
        int right=array.length-1;
        int par=partition(array,left,right);
        Stack<Integer> stack=new Stack<>();
        if(par>left+1){//左树有两个以上元素
            stack.push(left);//先放左 再放右
            stack.push(par-1);
        }
        if(par<right-1){//右树有两个以上元素
            stack.push(par+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            par=partition(array,left,right);
            if(par>left+1){//左树有两个以上元素
                stack.push(left);//先放左 再放右
                stack.push(par-1);
            }
            if(par<right-1){//右树有两个以上元素
                stack.push(par+1);
                stack.push(right);
            }
        }

    }


    private int mid(int []array,int start,int end){//三数取中
        int mid=(start+end)/2;
        if (array[start] < array[end]) {
            if(array[mid]<array[start]){
                return  start;
            }else if(array[mid]>array[end]){
                return end;
            }else{
                return mid;
            }
        }else{
            if(array[mid]<array[end]){
                return end;
            }else if(array[mid]>array[start]){
                return start;
            }else {
                return mid;
            }

        }

    }
    private int  partition(int []array,int start,int end){//将左右进行划分，并返回交换后的基准元素位置
        int i=start;
        while(start<end) {
            while (start<end&& array[end] >= array[i]) {//不加等号可能会使代码死循环，start和end始终不会相遇
                end--;
            }
            while (start<end&& array[start] <= array[i]) {
                start++;
            }
            swap(start, end, array);
        }
        swap(i,end,array);
        return end;
    }

    private int partition1(int []array,int start,int end){//玩坑法: 先将左侧基准值为坑，right找到小于的值时放入坑中，此时right为坑，left找大于的值再放入坑中.... 直到相遇结束
    int priot=array[start];
    while(start<end){
        while(start<end&&array[end]>=priot){
            end--;
        }
        array[start]=array[end];
        while(start<end&&array[start]<=priot){
            start++;
        }
        array[end]=array[start];
    }
    array[start]=priot;//此时start=end 为相遇时的位置
    return start;
    }

    private void intervalInsertSort(int []array,int start,int end){
        for (int i = start+1; i < end; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=start ; j--) {
                if(tmp<array[j]){
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }

    }

    public void mergeSort(int []array){
        mergeSortFunc(array,0,array.length-1);
    }

    private void mergeSortFunc(int []array, int left, int right){//实现递归的函数
        if(left==right)return;//当分割到只有一个时结束分割
        int mid=(right+left)/2;
        mergeSortFunc(array,left,mid);//左侧
        mergeSortFunc(array,mid+1,right);//右侧
        //合并  将左右两侧的数组进行合并
        merge(array,left,right,mid);
    }

    private void merge(int[]array,int left,int right,int mid){//进行顺序合并的函数
     int s1=left;
     int e1=mid;
     int s2=mid+1;
     int e2=right;
     int []index=new int[right-left+1];
     int i=0;
     while(s1<=e1&&s2<=e2){
         if(array[s1]<=array[s2]){
            index[i++]=array[s1++];
         }else{
             index[i++]=array[s2++];
         }
     }
     while(s1<=e1){
         index[i++]=array[s1++];
     }
     while(s2<=e2){
         index[i++]=array[s2++];
     }
        for(int j=0;j<index.length;j++){//array[j+left]就是在真实数组中的位置,即从left下标的位置开始
        array[j+left]=index[j];
        }
    }
    public void nonRecursiveMergeSort(int []array){// 用gap标记当前的合并的一个组合的数据元素个数
    int gap=1;
    while(gap<=array.length){
        for (int i = 0; i <array.length ; i+=gap*2) {//i从0开始进行每组的遍历
            int left=i;
            int mid=i+gap-1;
            if(mid>=array.length){
                mid= array.length-1;
            }
            int right=i+gap*2-1;
            if(right>=array.length){
                right= array.length-1;
            }
            merge(array,left,right,mid);
        }
        gap*=2;//回到上一组
    }
    }

}
